NFGen | 自动化非线性函数评估代码生成器

这次介绍的论文是清华团队Xiaoyu Fan等人发表在CCS'2022上的论文NFGen。论文链接如下：
https://dl.acm.org/doi/10.1145/3548606.3560565

本文针对MPC下开销巨大的非线性函数计算，提出了NFGen工具包。NFGen利用离散分段多项式，自动化综合考虑后端MPC协议的开销、近似精度等指标，生成最优的近似多项式，并利用后端的MPC协议库进行计算（例如PrivPy，MP-SPDZ等）。相比于之前手动在MPC源码下直接编写近似多项式，NFGen在精度、性能等方面都有长足提升。

1

问题与挑战

目前MPC在理论上虽然能够支持任意函数的计算，但是在计算复杂非线性函数，比如,  等，还存在很多问题：

• 正确性与精度：为了效率考虑，目前大多数MPC协议还是需要将浮点数（FLP）转化为定点数（FXP）进行计算。该转化不仅会引起精度的损失，在一些极端的情况下会带来溢出等错误；
• 性能：更重要的，MPC协议的计算性能比对应的明文计算低好几个数量级，尤其是针对复杂的非线性函数；
• 泛化性：即便我们可以用MPC协议内置支持的一些基本操作实现很多非线性函数，但是有些复杂的函数比如等还是很难去实现；
• 可移植性：MPC协议底层技术多样，针对不同的场景硬件环境等各种权衡复杂。如何设计面向多样化场景的最优方案是个难题。

针对上述难题，本文提出了NFGen。NFGen利用最基本的算子来实现多项式近似。由于这些基本算子被广泛支持，因此可以很容易对接不同的MPC协议库。挑战：针对一个非线性函数，获得一个FXP下面向MPC协议库的良好-分段近似多项式是本文面临的最大技术挑战，其中表示分段，表示分段多项式最大的阶数（degree）：

1. FXP下近似多项式的挑战：1）首先多项式需要满足FXP的值域和放缩限制，保证计算中间结果不溢出（上溢出、下溢出）；2）其次，FXP实际上是整数，寻找一个最优的多项式是一个NP-完全的整数规划问题。因此，本文需要寻找一个合理的近似。
2. 和的权衡：越大，则分段越多，因此需要的比较也越多；越大，则需要的乘法也越多。

如上图所示，NFGen工作流程如下：

1. 给定函数和系统配置文件NFD，NFGen首先在明文下计算函数得到候选定点数函数簇；
2. 进一步，根据MPC性能文件PPD从选取性能最优的函数；
3. 最后，利用生成代码模板OPPE，并生成后端MPC协议对应的代码。

2

方案设计符号和假设：令表示目标浮点数连续函数，表示近似区间；候选近似定点数多项式簇，其中表示该多项式在上分为段，每一段有近似多项式。当不太重要时，本文忽略的描述。表示-FXP定点数，其中为全部比特位长，为小数部分比特位长。2.1 非线性近似 非线性近似模块分为FitPiecewise和FitOnePiece两个主要模块。2.1.1 FitPiecewise 如算法1所示，该模块采用递归的方法对每一段调用FitOnePiece进行近似。如果当前分段无法达到近似精度，则进对当前分段进一步分为小段进行近似。最后的结果，为了减少分段数量，则尝试将相邻的分段合并。2.1.2 FitOnePiece 该部分是NFGen近似算法的核心，目标是针对一段进行多项式近似。给定，近似定点数多项式的目标是在算法2的近似计算中，首先需要解决确定合适的，以尽可能避免溢出问题：在过大时，可能会上溢出，在过小时，可能会下溢出，尤其是过大时。为了解决该问题，本文提出了算法。该方法的核心思想如下：   1. 为了防止上溢出，需要在时保证

;

2. 下溢出的情况则复杂一些：如果，那么存在。此时，令  ；否则当时，需要满足

。

最后具体算法如下：

确定之后，则在内进行采点，进行插值计算得到浮点数近似多项式，进而将浮点数近似多项式转化为定点数。转化时则会面临如下两个挑战：系数下溢出：当系数过小时，需要在比特的高位部分保留过多的，损失了高位的比特，而且当会引起下溢出。更严重的当时，可能越小； 近似精度损失：另一方面，将浮点转化为定点数，舍弃位及其之后的小数部分，会损失大量精度。为了尽可能解决上述问题，NFGen提出了如下策略：利用放缩因子增大表示范围：为了缓解系数下溢出问题，本文提出将浮点数系数转化为两个定点数使得，其中是一个放缩因子。从而使得保留尽可能多的高比特位。不过，本文也需要保证：

1. 不能太大，以免上溢出，即；

 2.    是一个合法的FXP且。具体算法如下:

具体算法如下：其中如下：利用残差提升精度：对于目标函数和近似函数，定义残差函数。进一步，本文再利用多项式近似估计，并进一步更新为，其中。具体算法构造如下：最后，算法2在定义域内采样一些随机点，测试近似多项式是否满足精度要求。2.2 OPPE 设计如算法7所示，多项式的安全计算遵循底层协议的计算，并且本文也利用了SIMD等MPC库广泛支持的优化算法提升性效率。3

实验评估

本文做了大量的实验，本博客只选择其中两部分说明：表2中A-F表示不同的开源协议库。对于一些表中的非线性函数计算,，NFGen大多数获得了在精度、通信和时间方面的提升。但是有些协议库都某些函数进行了高度优化，NFGen跟这些方案比还略优逊色。另一个实验，则是针对LR回归。和PrivPy相比，性能方面获得了很好的提升。其他实验和细节内容见原文。
译者简介：董业，本科毕业于山东大学计算机科学与技术专业，目前在中国科学院信息工程研究所攻读博士学位。主要研究兴趣包括隐私保护、安全多方计算、同态加密和机器学习。知乎：酸菜鱼。

END

往期推荐

TDSC 2022 | 为安全联邦学习建立互信的多混洗框架
隐私信息检索拓展应用
2023年度腾讯犀牛鸟精英人才计划——隐私保护相关课题
联邦学习 | 国内最新研究成果整理

欢迎投稿邮箱：[e-mail]参与更多讨论，请添加小编微信加入交流群